package vip.zhenzicheng.algorithm.demo.find;

/**
 * 只找一个局部最小值
 *
 * @author zhenzicheng
 * @date: 2022-05-18 18:58
 */
public class BSAwesome {

  /**
   * arr整体无序
   * arr相邻的数不相等
   */
  public static int oneMinIndex(int[] arr) {
    if (arr == null || arr.length == 0) {
      return -1;
    }
    int N = arr.length;
    if (N == 1) {
      return 0;
    }
    int L = 0;
    int R = N - 1;
    int ans = -1;

    // 局部最小值最少需要[L,R]上存在2个数，如果只有两个数则直接返回 [L] > [R] ? L : R
    while (L < R - 1) {
      int mid = (L + R) / 2;
      // 直接命中局部最小
      if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
        return mid;
      } else {
        if (arr[mid] > arr[mid - 1]) {
          R = mid - 1; // 收缩右边界
        } else {
          L = mid + 1;
        }
      }
    }

    return ans;
  }

  /**
   * 对数器 生成相邻数不相等的随机数组
   */
  public static int[] randomArray(int maxLen, int maxValue) {
    int len = (int) (Math.random() * maxLen);
    int[] arr = new int[len];
    if (len > 0) {
      arr[0] = (int) (Math.random() * maxValue);
      for (int i = 1; i < len; i++) {
        do {
          arr[i] = (int) (Math.random() * maxValue);
        } while (arr[i] == arr[i - 1]);
      }
    }
    return arr;
  }

  // 验证
  public static boolean check(int[] arr, int minIndex) {
    if (arr.length == 0) {
      return minIndex == -1;
    }

    int left = minIndex - 1;
    int right = minIndex + 1;
    // 判断是否指定位置元素的左边更大，如果超出范围则认为是
    boolean leftBigger = left >= 0 ? arr[left] > arr[minIndex] : true;
    boolean rightBigger = right <= arr.length ? arr[right] > arr[minIndex] : true;

    return leftBigger && rightBigger;
  }

}
